//1486. 数组异或操作

//给你两个整数，n 和 start 。
//数组 nums 定义为：nums[i] = start + 2 * i（下标从 0 开始）且 n == nums.length 。
//请返回 nums 中所有元素按位异或（XOR）后得到的结果。

//class Solution {
//    int xor_n(int n) {
//        switch (n % 4) {
//        case 0: return n;
//        case 1: return 1;
//        case 2: return n + 1;
//        default: return 0;
//        }
//    }
//
//public:
//    int xorOperation(int n, int start) {
//        int a = start / 2;
//        int b = n & start & 1; // 都为奇数才是 1
//        return (xor_n(a + n - 1) ^ xor_n(a - 1)) * 2 + b;
//    }
//};

//1720. 解码异或后的数组

//未知 整数数组 arr 由 n 个非负整数组成。
//经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1, 0, 2, 1] 经编码后得到 encoded = [1, 2, 3] 。
//给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
//请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

//class Solution {
//public:
//    vector<int> decode(vector<int>& encoded, int first) {
//        int n = encoded.size() + 1;
//        vector<int> arr(n);
//        arr[0] = first;
//        for (int i = 1; i < n; i++) {
//            arr[i] = arr[i - 1] ^ encoded[i - 1];
//        }
//        return arr;
//    }
//};

//2433. 找出前缀异或的原始数组

//给你一个长度为 n 的 整数 数组 pref 。找出并返回满足下述条件且长度为 n 的数组 arr ：
//pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].
//注意 ^ 表示 按位异或（bitwise - xor）运算。
//可以证明答案是 唯一 的。

//class Solution {
//public:
//    vector<int> findArray(vector<int>& pref) {
//        int n = pref.size();
//        vector<int> ans(n);
//        ans[0] = pref[0];
//        for (int i = 1; i < n; i++) {
//            ans[i] = pref[i] ^ pref[i - 1];
//        }
//        return ans;
//    }
//};

//1310. 子数组异或查询

//有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。
//对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li + 1] xor ... xor arr[Ri]）作为本次查询的结果。
//并返回一个包含给定查询 queries 所有结果的数组。

//class Solution {
//public:
//    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
//        int n = arr.size();
//        vector<int> xors(n + 1);
//        for (int i = 0; i < n; i++) {
//            xors[i + 1] = xors[i] ^ arr[i];
//        }
//        int m = queries.size();
//        vector<int> ans(m);
//        for (int i = 0; i < m; i++) {
//            ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1];
//        }
//        return ans;
//    }
//};

//2683. 相邻值的按位异或

//下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 按位异或（⊕）派生而来。
//特别地，对于范围[0, n - 1] 内的每个下标 i ：
//如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
//否则 derived[i] = original[i] ⊕ original[i + 1]
//给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。
//如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。
//二进制数组是仅由 0 和 1 组成的数组。

//class Solution {
//public:
//    bool doesValidArrayExist(vector<int>& derived) {
//        return reduce(derived.begin(), derived.end(), 0, bit_xor()) == 0;
//    }
//};

//1829. 每个查询的最大异或值

//给你一个 有序 数组 nums ，它由 n 个非负整数组成，同时给你一个整数 maximumBit 。你需要执行以下查询 n 次：
//找到一个非负整数 k < 2maximumBit ，使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length - 1] XOR k 的结果 最大化 。k 是第 i 个查询的答案。
//从当前数组 nums 删除 最后 一个元素。
//请你返回一个数组 answer ，其中 answer[i]是第 i 个查询的结果。

//class Solution {
//public:
//    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
//        int n = nums.size();
//        int mask = (1 << maximumBit) - 1;
//        int xorsum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
//
//        vector<int> ans;
//        for (int i = n - 1; i >= 0; --i) {
//            ans.push_back(xorsum ^ mask);
//            xorsum ^= nums[i];
//        }
//        return ans;
//    }
//};

//2997. 使数组异或和等于 K 的最少操作次数

//给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。
//你可以对数组执行以下操作 任意次 ：
//选择数组里的 任意 一个元素，并将它的 二进制 表示 翻转 一个数位，翻转数位表示将 0 变成 1 或者将 1 变成 0 。
//你的目标是让数组里 所有 元素的按位异或和得到 k ，请你返回达成这一目标的 最少 操作次数。
//注意，你也可以将一个数的前导 0 翻转。比方说，数字(101)2 翻转第四个数位，得到(1101)2 。

//class Solution {
//public:
//    int minOperations(vector<int>& nums, int k) {
//        int sum = reduce(nums.begin(), nums.end(), k, bit_xor());
//        return popcount(static_cast<uint32_t>(sum));
//    }
//};

//1442. 形成两个异或相等数组的三元组数目

//给你一个整数数组 arr 。
//现需要从数组中取三个下标 i、j 和 k ，其中(0 <= i < j <= k < arr.length) 。
//a 和 b 定义如下：
//a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
//b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
//注意： ^ 表示 按位异或 操作。
//
//请返回能够令 a == b 成立的三元组(i, j, k) 的数目。

//class Solution {
//public:
//    int countTriplets(vector<int>& arr) {
//        int n = arr.size();
//        unordered_map<int, int> cnt, total;
//        int ans = 0, s = 0;
//        for (int k = 0; k < n; ++k) {
//            int val = arr[k];
//            if (cnt.count(s ^ val)) {
//                ans += cnt[s ^ val] * k - total[s ^ val];
//            }
//            ++cnt[s];
//            total[s] += k;
//            s ^= val;
//        }
//        return ans;
//    }
//};

//2429. 最小异或

//给你两个正整数 num1 和 num2 ，找出满足下述条件的正整数 x ：
//x 的置位数和 num2 相同，且
//x XOR num1 的值 最小
//注意 XOR 是按位异或运算。
//返回整数 x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。
//整数的 置位数 是其二进制表示中 1 的数目。

//class Solution {
//public:
//    int minimizeXor(int num1, int num2) {
//        int c1 = popcount(static_cast<uint32_t>(num1));
//        int c2 = popcount(static_cast<uint32_t>(num2));
//        for (; c2 < c1; c2++) num1 &= num1 - 1; // 最低的 1 变成 0
//        for (; c2 > c1; c2--) num1 |= num1 + 1; // 最低的 0 变成 1
//        return num1;
//    }
//};

//2527. 查询数组异或美丽值

//给你一个下标从 0 开始的整数数组 nums 。
//三个下标 i ，j 和 k 的 有效值 定义为((nums[i] | nums[j]) & nums[k]) 。
//一个数组的 异或美丽值 是数组中所有满足 0 <= i, j, k < n  的三元组(i, j, k) 的 有效值 的异或结果。
//请你返回 nums 的异或美丽值。
//注意：
//val1 | val2 是 val1 和 val2 的按位或。
//val1 & val2 是 val1 和 val2 的按位与。

//class Solution {
//public:
//    int xorBeauty(vector<int>& nums) {
//        int ans = 0;
//        for (int x : nums) ans ^= x;
//        return ans;
//    }
//};

//2317. 操作后的最大异或和

//给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND(nums[i] XOR x) 。
//注意，AND 是逐位与运算，XOR 是逐位异或运算。
//请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。

//class Solution {
//public:
//    int maximumXOR(vector<int>& nums) {
//        int ans = 0;
//        for (int num : nums) ans |= num;
//        return ans;
//    }
//};

//2588. 统计美丽子数组数目

//给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
//选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
//选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
//将 nums[i] 和 nums[j] 都减去 2k 。
//如果一个子数组内执行上述操作若干次（包括 0 次）后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
//请你返回数组 nums 中 美丽子数组 的数目。
//子数组是一个数组中一段连续 非空 的元素序列。
//注意：所有元素最初都是 0 的子数组被认为是美丽的，因为不需要进行任何操作。

//class Solution {
//public:
//    long long beautifulSubarrays(vector<int>& nums) {
//        long long ans = 0;
//        int s = 0;
//        unordered_map<int, int> cnt{ {0, 1} };
//        for (int x : nums) {
//            s ^= x;
//            ans += cnt[s]++;
//        }
//        return ans;
//    }
//};

//2564. 子字符串异或查询

//给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [firsti, secondi] 。
//对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ，换言之，val ^ firsti == secondi 。
//第 i 个查询的答案是子字符串[lefti, righti] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为[-1, -1] 。如果有多个答案，请你选择 lefti 最小的一个。
//请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。
//子字符串 是一个字符串中一段连续非空的字符序列。

//class Solution {
//public:
//    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
//        unordered_map<int, pair<int, int>> m;
//        if (auto i = s.find('0'); i != string::npos) {
//            m[0] = { i, i };
//        }
//        for (int l = 0, n = s.length(); l < n; l++) {
//            if (s[l] == '0') {
//                continue;
//            }
//            for (int r = l, x = 0; r < min(l + 30, n); r++) {
//                x = (x << 1) | (s[r] & 1);
//                if (!m.contains(x)) {
//                    m[x] = { l, r };
//                }
//            }
//        }
//
//        vector<vector<int>> ans;
//        for (auto& q : queries) {
//            auto it = m.find(q[0] ^ q[1]);
//            if (it == m.end()) {
//                ans.push_back({ -1, -1 });
//            }
//            else {
//                ans.push_back({ it->second.first, it->second.second });
//            }
//        }
//        return ans;
//    }
//};

//1734. 解码异或后的排列

//给你一个整数数组 perm ，它是/*前 n 个正整数的排列*/，且 n 是个 奇数 。
//它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1, 3, 2] ，那么 encoded = [2, 1] 。
//给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。

//class Solution {
//public:
//    vector<int> decode(vector<int>& encoded) {
//        int n = encoded.size() + 1;
//        int total = 0;
//        for (int i = 1; i <= n; i++) {
//            total ^= i;
//        }
//        int odd = 0;
//        for (int i = 1; i < n - 1; i += 2) {
//            odd ^= encoded[i];
//        }
//        vector<int> perm(n);
//        perm[0] = total ^ odd;
//        for (int i = 0; i < n - 1; i++) {
//            perm[i + 1] = perm[i] ^ encoded[i];
//        }
//        return perm;
//    }
//};

//2857. 统计距离为 k 的点对

//给你一个 二维 整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [xi, yi] 是第 i 个点在二维平面里的坐标。
//我们定义两个点(x1, y1) 和(x2, y2) 的 距离 为(x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。
//请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。

//class Solution {
//public:
//    int countPairs(vector<vector<int>>& coordinates, int k) {
//        int ans = 0;
//        unordered_map<long long, int> cnt;
//        for (auto& p : coordinates) {
//            for (int i = 0; i <= k; i++) {
//                auto it = cnt.find((p[0] ^ i) * 2000000ll + (p[1] ^ (k - i)));
//                if (it != cnt.end()) {
//                    ans += it->second;
//                }
//            }
//            cnt[p[0] * 2000000ll + p[1]]++;
//        }
//        return ans;
//    }
//};

//1803. 统计异或值在范围内的数对有多少

//给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。
//漂亮数对 是一个形如(i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。

//class Solution {
//public:
//    int countPairs(vector<int>& nums, int low, int high) {
//        int ans = 0;
//        unordered_map<int, int> cnt;
//        for (int x : nums) ++cnt[x];
//        for (++high; high; high >>= 1, low >>= 1) {
//            unordered_map<int, int> nxt;
//            for (auto& [x, c] : cnt) {
//                if (high & 1 && cnt.count(x ^ (high - 1))) ans += c * cnt[x ^ (high - 1)];
//                if (low & 1 && cnt.count(x ^ (low - 1)))   ans -= c * cnt[x ^ (low - 1)];
//                nxt[x >> 1] += c;
//            }
//            cnt = move(nxt);
//        }
//        return ans / 2;
//    }
//};